{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Prison Cells After N Days"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: prisonAfterNDays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #N 天后的牢房"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>监狱中 <code>8</code> 间牢房排成一排，每间牢房可能被占用或空置。</p>\n",
    "\n",
    "<p>每天，无论牢房是被占用或空置，都会根据以下规则进行变更：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。</li>\n",
    "\t<li>否则，它就会被空置。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意</strong>：由于监狱中的牢房排成一行，所以行中的第一个和最后一个牢房不存在两个相邻的房间。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>cells</code> ，用于表示牢房的初始状态：如果第 <code>i</code> 间牢房被占用，则 <code>cell[i]==1</code>，否则 <code>cell[i]==0</code> 。另给你一个整数 <code>n</code> 。</p>\n",
    "\n",
    "<p>请你返回 <code>n</code> 天后监狱的状况（即，按上文描述进行 <code>n</code> 次变更）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cells = [0,1,0,1,1,0,0,1], n = 7\n",
    "<strong>输出：</strong>[0,0,1,1,0,0,0,0]\n",
    "<strong>解释：</strong>下表总结了监狱每天的状况：\n",
    "Day 0: [0, 1, 0, 1, 1, 0, 0, 1]\n",
    "Day 1: [0, 1, 1, 0, 0, 0, 0, 0]\n",
    "Day 2: [0, 0, 0, 0, 1, 1, 1, 0]\n",
    "Day 3: [0, 1, 1, 0, 0, 1, 0, 0]\n",
    "Day 4: [0, 0, 0, 0, 0, 1, 0, 0]\n",
    "Day 5: [0, 1, 1, 1, 0, 1, 0, 0]\n",
    "Day 6: [0, 0, 1, 0, 1, 1, 0, 0]\n",
    "Day 7: [0, 0, 1, 1, 0, 0, 0, 0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cells = [1,0,0,1,0,0,1,0], n = 1000000000\n",
    "<strong>输出：</strong>[0,0,1,1,1,1,1,0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>cells.length == 8</code></li>\n",
    "\t<li><code>cells[i]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [prison-cells-after-n-days](https://leetcode.cn/problems/prison-cells-after-n-days/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [prison-cells-after-n-days](https://leetcode.cn/problems/prison-cells-after-n-days/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,0,1,1,0,0,1]\\n7', '[1,0,0,1,0,0,1,0]\\n1000000000']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = n % 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        new_status = [0] * len(cells)\n",
    "        for day in range(n):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "        return new_status\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        def next_day(cells):\n",
    "            new_cells = [0] * 8\n",
    "            for i in range(1, 7):\n",
    "                if cells[i-1] == cells[i+1]:\n",
    "                    new_cells[i] = 1\n",
    "            return new_cells\n",
    "        \n",
    "        if n == 0:\n",
    "            return cells\n",
    "        \n",
    "        cells = next_day(cells)\n",
    "        n -= 1\n",
    "        \n",
    "        cycle_cells = next_day(cells)\n",
    "        cycle_count = 1\n",
    "        \n",
    "        while cycle_cells != cells:\n",
    "            cycle_cells = next_day(cycle_cells)\n",
    "            cycle_count += 1\n",
    "        \n",
    "        n %= cycle_count\n",
    "        \n",
    "        for _ in range(n):\n",
    "            cells = next_day(cells)\n",
    "        \n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = n % 14\n",
    "        if n == 0:\n",
    "            n = 14\n",
    "        while n > 0:\n",
    "            cells = Solution.fun1(cells)\n",
    "            n -= 1\n",
    "        return cells\n",
    "    def fun1(cells):\n",
    "        m = len(cells)\n",
    "        res = [0] * m\n",
    "        for i in range(1, m - 1):\n",
    "            if cells[i - 1] == cells[i + 1]:\n",
    "                res[i] = 1\n",
    "            else:\n",
    "                res[i] = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def nextDay(alist):\n",
    "         return [0] + [1 if alist[i-1] == alist[i+1] else 0 for i in range(1, 7)] + [0]\n",
    "\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        period = -1\n",
    "        dic_cells = set()\n",
    "        preCells = copy.deepcopy(cells)\n",
    "        for i in range(1, n+1):\n",
    "            curCells = self.nextDay(preCells)\n",
    "            if tuple(curCells) in dic_cells:\n",
    "                period = i - 1\n",
    "                break\n",
    "            dic_cells.add(tuple(curCells))\n",
    "            preCells = curCells\n",
    "\n",
    "        # print(period, n / period)\n",
    "        if period == -1:\n",
    "            return curCells\n",
    "        if n % period == 0:\n",
    "            return preCells\n",
    "        least = n % period - 1\n",
    "        # print('least:', least)\n",
    "        # print(curCells)\n",
    "        for i in range(least):\n",
    "            curCells = self.nextDay(curCells)\n",
    "        return curCells\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        \n",
    "        n = n % 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        new_status = [0] * len(cells)\n",
    "        print(len(cells) - 1)\n",
    "        for _ in range(n):\n",
    "            for i in range(1, 7):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "        \n",
    "        return new_status"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: list[int], n: int) -> list[int]:\n",
    "        n %= 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        new_status = [0] * (len(cells))\n",
    "        for day in range(n):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i - 1] ^ cells[i + 1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "        return new_status\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    cells = [0, 1, 0, 1, 1, 0, 0, 1]\n",
    "    n = 7\n",
    "    print(obj.prisonAfterNDays(cells, n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def prisonAfterNDays(self, cells, N):\n",
    "        def nextday(cells):\n",
    "            return [int(i > 0 and i < 7 and cells[i-1] == cells[i+1])\n",
    "                    for i in range(8)]\n",
    "\n",
    "        seen = {}\n",
    "        while N > 0:\n",
    "            c = tuple(cells)\n",
    "            if c in seen:\n",
    "                N %= seen[c] - N\n",
    "            seen[c] = N\n",
    "\n",
    "            if N >= 1:\n",
    "                N -= 1\n",
    "                cells = nextday(cells)\n",
    "\n",
    "        return cells\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def nextDay(alist):\n",
    "         return [0] + [1 if alist[i-1] == alist[i+1] else 0 for i in range(1, 7)] + [0]\n",
    "\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        period = -1\n",
    "        seen = set()\n",
    "        cur = copy.deepcopy(cells)\n",
    "        for i in range(1, n+1):\n",
    "            pos = self.nextDay(cur)\n",
    "            if tuple(pos) in seen:\n",
    "                period = i - 1\n",
    "                break\n",
    "            seen.add(tuple(pos))\n",
    "            cur = pos\n",
    "\n",
    "        if period == -1:\n",
    "            return pos\n",
    "        if n % period == 0:\n",
    "            return cur\n",
    "        least = n % period - 1\n",
    "        for i in range(least):\n",
    "            pos = self.nextDay(pos)\n",
    "        return pos\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:\n",
    "        states = []\n",
    "        c = 0\n",
    "        for idx in range(N):\n",
    "            cells = [0] + [1*(cells[i-1] == cells[i+1]) for i in range(1, 7)] + [0]\n",
    "            if cells in states:\n",
    "                c = idx\n",
    "                break\n",
    "            states.append(cells)\n",
    "        \n",
    "        if c == 0:\n",
    "            return cells\n",
    "        else:\n",
    "            return states[(N-1)%c]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        def nextday(cells):\n",
    "            return [int(i > 0 and i < 7 and cells[i-1] == cells[i+1])\n",
    "                    for i in range(8)]\n",
    "\n",
    "        seen = {}\n",
    "        while n > 0:\n",
    "            c = tuple(cells)\n",
    "            if c in seen:\n",
    "                n %= seen[c] - n\n",
    "            seen[c] = n\n",
    "\n",
    "            if n >= 1:\n",
    "                n -= 1\n",
    "                cells = nextday(cells)\n",
    "\n",
    "        return cells\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        def tran(cells):\n",
    "            ans = [0] * 8\n",
    "            for i in range(1, 7):\n",
    "                if cells[i - 1] == cells[i + 1]:\n",
    "                    ans[i] = 1\n",
    "            return ans\n",
    "\n",
    "        start = tran(cells)\n",
    "        cells = tran(start)\n",
    "        n -= 1\n",
    "        if n == 0:\n",
    "            return start\n",
    "        count = 1\n",
    "        while cells != start:\n",
    "            cells = tran(cells)\n",
    "            count += 1\n",
    "        rest = n % count\n",
    "        for _ in range(rest):\n",
    "            cells = tran(cells)\n",
    "        return cells\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n %= 14\n",
    "        if not n: n = 14\n",
    "        c = [0] * 8\n",
    "        for k in range(n):\n",
    "            for i in range(1, 7):\n",
    "                if cells[i-1] == cells[i+1]:\n",
    "                    c[i] = 1\n",
    "                else:\n",
    "                    c[i] = 0\n",
    "            cells = deepcopy(c)          \n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        rec = []\n",
    "        def go():\n",
    "            last = cells[0]\n",
    "            for i in range(1,7):\n",
    "                if last == cells[i + 1]:\n",
    "                    last = cells[i]\n",
    "                    cells[i] = 1\n",
    "                else:\n",
    "                    last = cells[i]\n",
    "                    cells[i] = 0\n",
    "            cells[0] = 0\n",
    "            cells[-1] = 0\n",
    "        flag = False\n",
    "        for idx in range(n):\n",
    "            go()\n",
    "            for i, cell in enumerate(rec):\n",
    "                if cell == \"\".join(map(str,cells)):\n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag:\n",
    "                break\n",
    "            rec.append(\"\".join(map(str,cells)))\n",
    "        if idx < n - 1:\n",
    "            T = len(rec) - i\n",
    "            idx2 = (n - i - 1) % T\n",
    "            return [int(i) for i in rec[i + idx2]]\n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        m = len(cells)\n",
    "        ss = []\n",
    "        pre = cells[0]\n",
    "        while True:\n",
    "            for j in range(1, m - 1):\n",
    "                curr = cells[j]\n",
    "                cells[j] = (pre ^ cells[j+1]) ^ 1\n",
    "                pre = curr\n",
    "            cells[0] = 0\n",
    "            cells[-1] = 0\n",
    "            pre = 0\n",
    "            if cells in ss:\n",
    "                break\n",
    "            ss.append(cells[:])\n",
    "\n",
    "        n = (n - 1) % len(ss)\n",
    "        return ss[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        def nextday(cells):\n",
    "            return [int(i > 0 and i < 7 and cells[i - 1] == cells[i + 1]) for i in range(8)]\n",
    "        if len(cells) != 8:\n",
    "            return cells\n",
    "        obever = {}\n",
    "        sum = 0\n",
    "        while n > 0:\n",
    "            sum += 1\n",
    "            c = tuple(cells)\n",
    "            if c in obever:\n",
    "                n %= obever[c] - n\n",
    "            obever[c] = n\n",
    "            if n >= 1:\n",
    "                n -= 1\n",
    "                cells = nextday(cells)\n",
    "        print(sum)\n",
    "        return cells\n",
    " \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        t = 0\n",
    "        for c in cells:\n",
    "            t <<= 1\n",
    "            t += c\n",
    "        \n",
    "        mask = (1 << 7) - 2\n",
    "        mp = dict()\n",
    "        arr = []\n",
    "        ans = None\n",
    "        for idx in range(1, n+1):\n",
    "            left = t << 1\n",
    "            right = t >> 1\n",
    "            t = ~(left ^ right)\n",
    "            t &= mask\n",
    "\n",
    "            if t in mp:\n",
    "                length = idx - mp[t]\n",
    "                res = (n - idx + 1) % length\n",
    "                if res == 0:\n",
    "                    res = length\n",
    "                t = arr[mp[t] - 1 + res-1]\n",
    "                break\n",
    "            else:\n",
    "                mp[t] = idx\n",
    "                arr.append(t)\n",
    "        \n",
    "        a = []\n",
    "        for idx in range(7, -1, -1):\n",
    "            a.append((t >> idx) & 1)\n",
    "        \n",
    "        return a \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        m = len(cells)\n",
    "        ss = []\n",
    "        pre = cells[0]\n",
    "        while True:\n",
    "            for j in range(1, m - 1):\n",
    "                curr = cells[j]\n",
    "                cells[j] = (pre ^ cells[j+1]) ^ 1\n",
    "                pre = curr\n",
    "            cells[0] = 0\n",
    "            cells[-1] = 0\n",
    "            pre = 0\n",
    "            if cells in ss:\n",
    "                break\n",
    "            ss.append(cells[:])\n",
    "\n",
    "        n = (n - 1) % len(ss)\n",
    "        return ss[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        states, ss, end, cur = [], set(), -1, cells\n",
    "        st = sum([cells[i] * (1 << i) for i in range(8)])\n",
    "        while True:\n",
    "            tmp = [0 for _ in range(8)]\n",
    "            for i in range(1, 7):\n",
    "                if cur[i - 1] == cur[i + 1]: tmp[i] = 1\n",
    "            cur = tmp\n",
    "            st = sum([cur[i] * (1 << i) for i in range(8)])\n",
    "            if st in ss: break\n",
    "            states.append(cur)\n",
    "            ss.add(st)\n",
    "            if len(states) == n: return cur\n",
    "        cycle = len(states)\n",
    "        rem = (n - 1) % cycle\n",
    "        return states[rem]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        def next_cell(cells):\n",
    "            return [int(x>0 and x<7 and cells[x-1] == cells[x+1]) for x in range(8)]\n",
    "        \n",
    "\n",
    "        seen = {}\n",
    "        while n > 0: \n",
    "            c = tuple(cells)\n",
    "            if c in seen:\n",
    "                # print('n in seen before is: ', n) #84\n",
    "                # print('seen[c] is: ', seen[c]) #98\n",
    "\n",
    "                # print('seen[c] - n is: ', seen[c] - n) #14\n",
    "\n",
    "                n %= seen[c] - n\n",
    "                # print('n after mod is: ', n) #0：此时应该直接return cells，而不cells = next_cell(cells)\n",
    "            seen[c] = n\n",
    "            if n >= 1: # must: cells= [1,0,0,0,1,0,0,1], n=99, see print. 只有n>0的时候才next_cell(cells)   \n",
    "                n -= 1\n",
    "\n",
    "                cells = next_cell(cells)\n",
    "        return cells\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = n % 14\n",
    "        if n == 0:\n",
    "            n = 14\n",
    "        for i in range(n):\n",
    "            list_temp = [0]*8\n",
    "            for cell in range(1, len(cells) - 1):\n",
    "                if cells[cell - 1] == cells[cell + 1]:\n",
    "                    list_temp[cell] = 1\n",
    "                else:\n",
    "                    list_temp[cell] = 0\n",
    "            cells = list_temp\n",
    "            cells[0], cells[-1] =0,0\n",
    "        cells[0],cells[-1] = 0, 0\n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        if n == 0:\n",
    "            return cells\n",
    "        new_status = [0] * len(cells)\n",
    "        for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "        first = new_status.copy()\n",
    "        cells = copy.deepcopy(new_status)\n",
    "        n = n-1\n",
    "        for day in range(n):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "            if new_status == first:\n",
    "                m = (n)%(day+1)\n",
    "                for d in range(m):\n",
    "                    for j in range(1, len(cells) - 1):\n",
    "                        new_status[j] = cells[j-1] ^ cells[j+1] ^ 1\n",
    "                    cells = copy.deepcopy(new_status)\n",
    "                return new_status\n",
    "        return new_status\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def nextDay(alist):\n",
    "         return [0] + [1 if alist[i-1] == alist[i+1] else 0 for i in range(1, 7)] + [0]\n",
    "\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        period = -1\n",
    "        seen = set()\n",
    "        cur = copy.deepcopy(cells)\n",
    "        for i in range(1, n+1):\n",
    "            pos = self.nextDay(cur)\n",
    "            if tuple(pos) in seen:\n",
    "                period = i - 1\n",
    "                break\n",
    "            seen.add(tuple(pos))\n",
    "            cur = pos\n",
    "\n",
    "        if period == -1:\n",
    "            return pos\n",
    "        if n % period == 0:\n",
    "            return cur\n",
    "        least = n % period - 1\n",
    "        for i in range(least):\n",
    "            pos = self.nextDay(pos)\n",
    "        return pos\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = n % 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        new_status = [0] * len(cells)\n",
    "        for day in range(n):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "        return new_status\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n %= 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        def get_next(li):\n",
    "            return [int(i > 0 and i < 7 and li[i - 1] == li[i + 1]) for i in range(8)]\n",
    "        for _ in range(n):\n",
    "            cells = get_next(cells)\n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        asource, tmp = None, [0]*8\n",
    "        cycle, k = 0, n\n",
    "        \n",
    "        while k:\n",
    "            for i in range(1, 7):\n",
    "                tmp[i] = int(cells[i-1] == cells[i+1])\n",
    "            \n",
    "            if cycle == 0:\n",
    "                source = tmp[::] \n",
    "            elif source == tmp:\n",
    "                k %= cycle\n",
    "\n",
    "            cells = tmp[::]\n",
    "            cycle += 1\n",
    "            k -= 1\n",
    "        \n",
    "        return cells\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        def tmdnk(A):\n",
    "            ans=[0 for i in range(8)]\n",
    "            for i in range(1,7):\n",
    "                if (A[i-1]+A[i+1])%2==0:\n",
    "                    ans[i]=1\n",
    "                else:\n",
    "                    ans[i]=0\n",
    "            return ans\n",
    "        i=0\n",
    "        B=collections.defaultdict(list)\n",
    "        A=collections.defaultdict(list)\n",
    "        while i<n:\n",
    "            cells=tmdnk(cells)\n",
    "            an=\"\"\n",
    "            for j in range(len(cells)):\n",
    "                an+=str(cells[j])\n",
    "            B[an].append(i)\n",
    "            A[i].append(an)\n",
    "            if len(B[an])==2:\n",
    "                break\n",
    "            i+=1\n",
    "        # print(A,B)\n",
    "        if i==n:\n",
    "            return cells\n",
    "        else:\n",
    "            zhuqi=B[an][1]-B[an][0]\n",
    "            BB=A[(n-1-B[an][0])%zhuqi+B[an][0]].pop()\n",
    "            ans=[]\n",
    "            for i in range(8):\n",
    "                ans.append(int(BB[i]))\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        def nextday(cells):\n",
    "            new_cells = [0]\n",
    "            for i in range(1, 7):\n",
    "                if cells[i - 1] == cells[i + 1]:\n",
    "                    new_cells.append(1)\n",
    "                else:\n",
    "                    new_cells.append(0)\n",
    "            new_cells.append(0)\n",
    "            return new_cells\n",
    "        \n",
    "        seen = {}\n",
    "        while n > 0:\n",
    "            c = tuple(cells)\n",
    "            if c in seen:\n",
    "                n %= seen[c] - n\n",
    "            else:\n",
    "                seen[c] = n \n",
    "            \n",
    "            if n >= 1:\n",
    "                n -= 1\n",
    "                cells = nextday(cells)\n",
    "        \n",
    "        return cells\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def nextDay(alist):\n",
    "         return [0] + [1 if alist[i-1] == alist[i+1] else 0 for i in range(1, 7)] + [0]\n",
    "\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        seen = set()\n",
    "        seen.add(tuple(cells))\n",
    "        cnt = 0\n",
    "        flag = 0\n",
    "        if cells[0] or cells[-1]:\n",
    "            flag = 1\n",
    "            cells = self.nextDay(cells)\n",
    "            n -= 1\n",
    "\n",
    "        while n > 0:\n",
    "            cells = self.nextDay(cells)\n",
    "            cnt += 1\n",
    "            n -= 1\n",
    "            if tuple(cells) in seen:\n",
    "                # print(\"cnt: \", cnt)\n",
    "                if flag == 1:\n",
    "                    cnt -= 1\n",
    "                n = n % (cnt)\n",
    "                seen = set()\n",
    "            seen.add(tuple(cells))\n",
    "\n",
    "        return cells\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        '''\n",
    "        period = -1\n",
    "        seen = set()\n",
    "        cur = copy.deepcopy(cells)\n",
    "        for i in range(1, n+1):\n",
    "            pos = self.nextDay(cur)\n",
    "            if tuple(pos) in seen:\n",
    "                period = i - 1\n",
    "                break\n",
    "            seen.add(tuple(pos))\n",
    "            cur = pos\n",
    "\n",
    "        if period == -1:\n",
    "            return pos\n",
    "        if n % period == 0:\n",
    "            return cur\n",
    "        least = n % period - 1\n",
    "        for i in range(least):\n",
    "            pos = self.nextDay(pos)\n",
    "        return pos\n",
    "        '''\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:\n",
    "        states = []\n",
    "        c = 0\n",
    "        for idx in range(N):\n",
    "            cells = [0] + [1*(cells[i-1] == cells[i+1]) for i in range(1, 7)] + [0]\n",
    "            if cells in states:\n",
    "                c = idx\n",
    "                break\n",
    "            states.append(cells)\n",
    "        \n",
    "        if c == 0:\n",
    "            return cells\n",
    "        else:\n",
    "            return states[N%c-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        cell_record = [cells]\n",
    "        for i in range(n):\n",
    "            next_cells = [0]\n",
    "            for j in range(1, len(cells)-1):\n",
    "                next_cells.append(1 if cells[j-1] == cells[j+1] else 0)\n",
    "            next_cells .append(0)\n",
    "            # 确定循环次数\n",
    "            if next_cells in cell_record:\n",
    "                index = cell_record.index(next_cells)  # 如果出现循环，则计算出现的循环的索引\n",
    "                loop = len(cell_record) - index        # 计算循环周期\n",
    "                cell_record = cell_record[index:]     \n",
    "                return cell_record[(n-index) % loop]   # 剩余循环次数//循环周期 \n",
    "            cell_record.append(next_cells[:])\n",
    "            cells = next_cells[:]\n",
    "        return cells\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = (n - 1) % 14 + 1\n",
    "        for _ in range(n):\n",
    "            cells = [0] + [cells[i-1] ^ cells[i+1] ^ 1 for i in range(1, 7)] + [0]\n",
    "        return cells\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:\n",
    "        def nextday(cells):\n",
    "            return [int(i > 0 and i < 7 and cells[i-1] == cells[i+1])\n",
    "                    for i in range(8)]\n",
    "\n",
    "        seen = {}\n",
    "        while N > 0:\n",
    "            c = tuple(cells)\n",
    "            if c in seen:\n",
    "                N %= seen[c] - N\n",
    "            seen[c] = N\n",
    "\n",
    "            if N >= 1:\n",
    "                N -= 1\n",
    "                cells = nextday(cells)\n",
    "\n",
    "        return cells\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        new_status = [0] * len(cells)\n",
    "        for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "        first = new_status.copy()\n",
    "        cells = copy.deepcopy(new_status)\n",
    "        n = n-1\n",
    "        for day in range(n):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "            if new_status == first:\n",
    "                m = (n)%(day+1)\n",
    "                for d in range(m):\n",
    "                    for j in range(1, len(cells) - 1):\n",
    "                        new_status[j] = cells[j-1] ^ cells[j+1] ^ 1\n",
    "                    cells = copy.deepcopy(new_status)\n",
    "                return new_status\n",
    "        return new_status\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: list[int], n: int) -> list[int]:\n",
    "        n %= 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        new_status = [0] * len(cells)\n",
    "        for day in range(n):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i - 1] ^ cells[i + 1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "        return new_status\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    cells = [0, 1, 0, 1, 1, 0, 0, 1]\n",
    "    n = 7\n",
    "    print(obj.prisonAfterNDays(cells, n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "\n",
    "        num_map = {}\n",
    "\n",
    "        def convert(c_list):\n",
    "            num = 0\n",
    "            x = 1\n",
    "            for i in range(8):\n",
    "                num += x * c_list[i]\n",
    "                x = x << 1\n",
    "            num_map[num] = c_list\n",
    "            return num\n",
    "\n",
    "        num_list = []\n",
    "        num_set = set({})\n",
    "        now_num = convert(cells)\n",
    "        num_list.append(now_num)\n",
    "        num_set.add(now_num)\n",
    "        for _ in range(64):\n",
    "            tmp_list = [0] * 8\n",
    "            for j in range(1, 7):\n",
    "                tmp_list[j] = 1 - cells[j-1] ^ cells[j+1]\n",
    "            cells = tmp_list\n",
    "            now_num = convert(cells)\n",
    "            if now_num in num_set:\n",
    "                break\n",
    "\n",
    "            num_list.append(now_num)\n",
    "            num_set.add(now_num)\n",
    "        now_num = convert(cells)\n",
    "        if n < len(num_list):\n",
    "            return num_map[num_list[n]]\n",
    "        now_num_index = num_list.index(now_num)\n",
    "        left_num_list = num_list[now_num_index:]\n",
    "        left = (n - len(num_list)) % len(left_num_list)\n",
    "        r_num = left_num_list[left]\n",
    "        return num_map[r_num]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "    l = len(cells)\n",
    "    r, rr = {}, {}\n",
    "    ps = cells\n",
    "    \n",
    "    c = 0\n",
    "    while c < n:\n",
    "      ns = [0] * l\n",
    "      c += 1\n",
    "      for i in range(1, l - 1):\n",
    "        if ps[i - 1] == ps[i + 1]:\n",
    "          ns[i] = 1\n",
    "        else:\n",
    "          ns[i] = 0\n",
    "      t = tuple(ns)\n",
    "      # print(f\"{t} @ {c}\")\n",
    "      if t in r:\n",
    "        print(f\"find dup {t} @{c} p {r[t]}\")\n",
    "        d = c - r[t]\n",
    "        r = {}\n",
    "        rr = {}\n",
    "        z = (n - c) // d\n",
    "        c = d * z + c\n",
    "        r[t] = c\n",
    "        rr[c] = t\n",
    "      else:\n",
    "        r[t] = c\n",
    "        rr[c] = t\n",
    "      ps = ns\n",
    "    return list(rr[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        The key is to find odd/even number states are determined by \n",
    "        odd/even number states after two iterations\n",
    "        Maximum 7 iterations to repeat\n",
    "        See https://math.stackexchange.com/questions/3311568/why-does-this-pattern-repeat-after-14-cycles-instead-of-256-can-you-give-a-proo/3311963#3311963\n",
    "        \"\"\"\n",
    "        \n",
    "        states = []\n",
    "        for idx in range(min(N, 14)):\n",
    "            cells = [0] + [1*(cells[i-1] == cells[i+1]) for i in range(1, 7)] + [0]\n",
    "            states.append(cells)\n",
    "        \n",
    "        if N <= 14:\n",
    "            return cells\n",
    "        else:\n",
    "            return states[(N-1)%14]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        cell_list = []\n",
    "        while True:\n",
    "            n -= 1\n",
    "            cells_old = cells[:]\n",
    "            cells[0] = 0\n",
    "            cells[-1] = 0\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                if cells_old[i - 1] == cells_old[i + 1]:\n",
    "                    cells[i] = 1\n",
    "                else:\n",
    "                    cells[i] = 0\n",
    "            # print(cells)\n",
    "            if n == 0:\n",
    "                return cells\n",
    "            if len(cell_list) == 0 or cells != cell_list[0]:\n",
    "                cell_list.append(cells[:])\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return cell_list[n % len(cell_list)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        cnt = 0\n",
    "        seen = {}\n",
    "        T, mod = 1, 0\n",
    "\n",
    "        while True:\n",
    "            cur_cells = [0] * 8\n",
    "            for i in range(1, 7):\n",
    "                cur_cells[i] = 1 if cells[i-1] == cells[i+1] else 0\n",
    "            \n",
    "            cnt += 1\n",
    "            if cnt == n:\n",
    "                return cur_cells\n",
    "            \n",
    "            c = tuple(cur_cells)\n",
    "            if c in seen:\n",
    "                T = cnt - seen[c]\n",
    "                mod = seen[c]\n",
    "                break\n",
    "            seen[c] = cnt\n",
    "            cells = cur_cells\n",
    "        \n",
    "        n = (n - mod) % T\n",
    "        n += mod\n",
    "        for key in seen:\n",
    "            if seen[key] == n:\n",
    "                return list(key)\n",
    "\n",
    "        return [0] * 8\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        def nextday(cells):\n",
    "            return [int(i>0 and i<7 and cells[i-1]==cells[i+1]) for i in range(8)]\n",
    "        rec = dict()\n",
    "        while n > 0:\n",
    "            c = tuple(cells)\n",
    "            if c in rec:\n",
    "                n %= rec[c] - n\n",
    "            rec[c] = n\n",
    "            if n >= 1:\n",
    "                n -= 1\n",
    "                cells = nextday(cells)\n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = n % 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        new_status = [0] * len(cells)\n",
    "        for day in range(n):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "        return new_status\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], k: int) -> List[int]:\n",
    "        n = len(cells)\n",
    "        # dp[i][j]表示状态i，经过2^j天的状态\n",
    "        mx_len = floor(log2(k))\n",
    "        dp = [[inf] * (mx_len + 1) for _ in range(1 << n)]\n",
    "\n",
    "        def move(state):\n",
    "            s1 = state << 1\n",
    "            s2 = state >> 1\n",
    "            # 相等时，返回1，否则返回0\n",
    "            ans = s1 ^ s2 ^ (0b11111111)\n",
    "            ans &= (0b01111110)\n",
    "            return ans\n",
    "\n",
    "        for i in range(1 << n):\n",
    "            dp[i][0] = move(i)\n",
    "            # print(i,dp[i][0])\n",
    "\n",
    "        for j in range(1, mx_len + 1):\n",
    "            for i in range(1 << n):\n",
    "                dp[i][j] = dp[dp[i][j - 1]][j - 1]\n",
    "\n",
    "        state = int(''.join(list(map(str, cells))), base=2)\n",
    "        for i in range(mx_len, -1, -1):\n",
    "            if k >> i & 1:\n",
    "                state = dp[state][i]\n",
    "        # 48 -> [0,0,1,1,0,0,0,0]\n",
    "        ans = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if state >> i & 1:\n",
    "                ans.append(1)\n",
    "            else:\n",
    "                ans.append(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n %= 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        new_status = [0] * 8\n",
    "        for _ in range(n):\n",
    "            for i in range(1, 7):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = deepcopy(new_status)\n",
    "        return new_status\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = n % 14\n",
    "        if not n: n = 14\n",
    "        new_status = [0]*len(cells)\n",
    "        for _ in range(n):\n",
    "            for i in range(1, len(cells)-1):\n",
    "                new_status[i] = 1 if cells[i-1] == cells[i+1] == 1 or cells[i-1] == cells[i+1] == 0 else 0\n",
    "            cells = new_status.copy()\n",
    "        return new_status"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        def next_cell(cells):\n",
    "            return [int(x>0 and x<7 and cells[x-1] == cells[x+1]) for x in range(8)]\n",
    "        \n",
    "\n",
    "        seen = {}\n",
    "        while n > 0: \n",
    "            c = tuple(cells)\n",
    "            if c in seen:\n",
    "                # print('n in seen before is: ', n) #84\n",
    "                # print('seen[c] is: ', seen[c]) #98\n",
    "\n",
    "                # print('seen[c] - n is: ', seen[c] - n) #14\n",
    "\n",
    "                n %= seen[c] - n #这句话让\"while n>0\" != \"if n>=1\"!\n",
    "                # print('n after mod is: ', n) #0：此时应该直接return cells，而不cells = next_cell(cells)\n",
    "            seen[c] = n\n",
    "            if n >= 1: # must: cells= [1,0,0,0,1,0,0,1], n=99, see print. 只有n>0的时候才next_cell(cells)   \n",
    "                n -= 1\n",
    "\n",
    "                cells = next_cell(cells) \n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n=n%14 if n%14!= 0 else 14\n",
    "        res = cells\n",
    "        for current_step in range(n):\n",
    "            # print(res)\n",
    "            # new_res = {0:0}\n",
    "            new_res = [0]\n",
    "            for i in range(1,len(res)):\n",
    "                try:\n",
    "                    element = 1 if res[i-1] == res[i+1] else 0\n",
    "                except:\n",
    "                    element = 0\n",
    "                new_res.append(element)\n",
    "            res = new_res\n",
    "\n",
    "        # res =  [res[x] for x in range(len(res))]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        def get_str(a):\n",
    "            return ''.join([str(i) for i in a])\n",
    "        d = {}\n",
    "        l = []\n",
    "        cycle_start = 0\n",
    "        cycle = 10**9+7\n",
    "        for i in range(n+1):\n",
    "            s = get_str(cells)\n",
    "            if s in d:\n",
    "                cycle_start = d[s]\n",
    "                cycle = i-d[s]\n",
    "                break\n",
    "            d[s]=i\n",
    "            l.append(s)\n",
    "            new_cells = [0]*len(cells)\n",
    "            for j in range(1,len(cells)-1):\n",
    "                if cells[j-1]==cells[j+1]:\n",
    "                    new_cells[j]=1\n",
    "            cells = new_cells\n",
    "        s = get_str(cells)\n",
    "        s = l[(n-cycle_start)%cycle+cycle_start]\n",
    "        cells = [int(i) for i in s]\n",
    "        return cells\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        def get_next(li):\n",
    "            return [int(i > 0 and i < 7 and li[i - 1] == li[i + 1]) for i in range(8)]\n",
    "        seen = dict()\n",
    "        while n > 0:\n",
    "            if tuple(cells) in seen:\n",
    "                n %= seen[tuple(cells)] - n\n",
    "            seen[tuple(cells)] = n\n",
    "            if n >= 1:\n",
    "                n -= 1\n",
    "                cells = get_next(cells)\n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        temp = [0, 0, 0, 0, 0, 0, 0, 0]\n",
    "        for i in range(n % 14 if n % 14 else 14):\n",
    "            for j in range(1, 7):\n",
    "                temp[j] = (cells[j - 1] ^ cells[j + 1]) ^ 1\n",
    "            cells = temp.copy()\n",
    "            print(cells)\n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = n % 14\n",
    "        if n == 0:\n",
    "            n = 14\n",
    "        for i in range(n):\n",
    "            if i == 1:\n",
    "                cells[0], cells[-1] = 0, 0\n",
    "            list_temp = [0]*8\n",
    "            for cell in range(1, len(cells) - 1):\n",
    "                if cells[cell - 1] == cells[cell + 1]:\n",
    "                    list_temp[cell] = 1\n",
    "                else:\n",
    "                    list_temp[cell] = 0\n",
    "            cells = list_temp\n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\r\n",
    "        n %= 14\r\n",
    "        if not n:\r\n",
    "            n = 14\r\n",
    "        new = [0] * 8\r\n",
    "        for day in range(n):\r\n",
    "            for i in range(1, 7):\r\n",
    "                new[i] = cells[i-1] ^ cells[i+1] ^ 1\r\n",
    "            cells = new[:]\r\n",
    "        return new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        seen = dict()\n",
    "        while n > 0:\n",
    "            seen[tuple(cells)] = n\n",
    "            n -= 1\n",
    "            cells = [0] + [cells[i - 1] ^ cells[i + 1] ^ 1 for i in range(1,7)] + [0]\n",
    "\n",
    "            if tuple(cells) in seen:\n",
    "                n %= seen[tuple(cells)] - n\n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = (n - 1) % 14 + 1\n",
    "        new_status = [0] * 8\n",
    "        for _ in range(n):\n",
    "            for i in range(1, 7):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = deepcopy(new_status)\n",
    "        return new_status\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = n % 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        new_status = [0] * len(cells)\n",
    "        for day in range(n):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "        return new_status\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextState(self, cells):\n",
    "        return [int(i > 0 and i < 7 and cells[i - 1] == cells[i + 1]) for i in range(8)]\n",
    "        \n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        seen = {}\n",
    "        while n > 0:\n",
    "\n",
    "            c = tuple(cells)\n",
    "            if c in seen:\n",
    "                n %= seen[c] - n\n",
    "            seen[c] = n\n",
    "            \n",
    "            if n >= 1:\n",
    "                n -= 1\n",
    "                cells = self.nextState(cells)\n",
    "\n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = n % 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        new_status = [0] * len(cells)\n",
    "        for day in range(n):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = copy.copy(new_status)\n",
    "        return new_status"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        if n == 0:\n",
    "            return cells\n",
    "        new_status = [0] * len(cells)\n",
    "        for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "        first = new_status.copy()\n",
    "        cells = copy.deepcopy(new_status)\n",
    "        for day in range(n-1):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "            if new_status == first:\n",
    "                m = (n-1)%(day+1)\n",
    "                for d in range(m):\n",
    "                    for j in range(1, len(cells) - 1):\n",
    "                        new_status[j] = cells[j-1] ^ cells[j+1] ^ 1\n",
    "                    cells = copy.deepcopy(new_status)\n",
    "                return new_status\n",
    "        return new_status\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        for _ in range((n - 1) % 14 + 1):\n",
    "            cells = [int(0 < i < 7 and cells[i-1] == cells[i+1]) for i in range(8)]\n",
    "        return cells\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        d=dict()\n",
    "        ls=[]\n",
    "        day=1\n",
    "        m=len(cells)\n",
    "        last=cells\n",
    "        ret=dict()\n",
    "        T=0\n",
    "        while day<=n:\n",
    "            #print(day,n)\n",
    "            now=[0]*m\n",
    "            for i in range(m):\n",
    "                if i==0 or i==m-1:\n",
    "                    continue\n",
    "                if last[i-1]==last[i+1]:\n",
    "                    now[i]=1\n",
    "            tp=tuple(now)\n",
    "            if tp in d:\n",
    "                T=day-d[tp]\n",
    "                break\n",
    "            d[tp]=day\n",
    "            ret[day]=tp\n",
    "            if day==n:\n",
    "                return now\n",
    "            day+=1\n",
    "            last=now\n",
    "        if T!=0:\n",
    "            k=n%T\n",
    "            while k<day-T:\n",
    "                k+=T\n",
    "            return list(ret[k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        # n = n % 14\n",
    "        # if not n:\n",
    "        #     n = 14\n",
    "        \n",
    "        # new_status = [0] * len(cells)\n",
    "        # for day in range(n):\n",
    "        #     for i in range(1, len(cells) - 1):\n",
    "        #         new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "        #     cells = copy.deepcopy(new_status)\n",
    "\n",
    "        # return new_status\n",
    "\n",
    "# 作者：fenciely\n",
    "\n",
    "\n",
    "        jk = [cells]\n",
    "        n = n % 14\n",
    "\n",
    "        for m in range(14):\n",
    "            k = [None]*8\n",
    "            k[0] = 0\n",
    "            k[-1] = 0\n",
    "            for i in range(1,7):\n",
    "                if (jk[m][i-1] == 0 and jk[m][i+1] == 0) or (jk[m][i-1] == 1 and jk[m][i+1] == 1):\n",
    "                    k[i] = 1\n",
    "                else:\n",
    "                    k[i] = 0\n",
    "            jk.append(k)\n",
    "\n",
    "        if n != 0:\n",
    "            return jk[n]\n",
    "        else:\n",
    "            return jk[14]\n",
    "\n",
    "# 作者：yan723\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = n % 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        new_status = [0] * len(cells)\n",
    "        for day in range(n):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i-1] ^ cells[i+1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "        return new_status\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import  List\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        res = [''.join([str(i) for i in cells])]\n",
    "        i = 0\n",
    "        while i<n:\n",
    "            temp = cells.copy()\n",
    "            for j in range(1,7):\n",
    "                if cells[j-1] == cells[j+1]:\n",
    "                    temp[j]=1\n",
    "                else:\n",
    "                    temp[j]=0\n",
    "            temp[0]=0\n",
    "            temp[-1] = 0\n",
    "            cells = temp\n",
    "            ans = ''.join([str(i) for i in cells])\n",
    "            if ans in res and n>10**5:\n",
    "                print(ans)\n",
    "                res.append(ans)\n",
    "                break\n",
    "            res.append(ans)\n",
    "            i+=1\n",
    "\n",
    "        if i<n:\n",
    "            ans = res.pop(-1)\n",
    "            print(ans,)\n",
    "            ids = res.index(ans)\n",
    "            print(len(res[ids:]),(n - ids+1) % (len(res[ids:])),ids,res[ids:])\n",
    "            temp = res[ids:]\n",
    "            ans = temp[(n - ids+1) % (len(res[ids:]))-1]\n",
    "            return [int(i) for i in ans]\n",
    "        else:\n",
    "            return [int(i) for i in res[-1]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        seen = set()\n",
    "        og = cells\n",
    "        def toDigit(cells):\n",
    "            return int('0b' + ''.join(map(str, cells)), 2)\n",
    "\n",
    "        def toCell(num):\n",
    "            res = [0] * 8\n",
    "\n",
    "            for i in range(8):\n",
    "                if num & (1 << i):\n",
    "                    res[8 - i - 1] = 1\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "        def convert(cells):\n",
    "            res = [0] * 8\n",
    "\n",
    "            for i in range(1, 7):\n",
    "                if cells[i - 1] == cells[i + 1]:\n",
    "                    res[i] = 1\n",
    "            return res\n",
    "\n",
    "        ll = []\n",
    "        while True:\n",
    "            val = toDigit(cells)\n",
    "            if val in seen:\n",
    "                break\n",
    "            else:\n",
    "                seen.add(val)\n",
    "                cells = convert(cells)\n",
    "                ll.append(val)\n",
    "\n",
    "        for i in range(len(ll)):\n",
    "            if ll[i] == val:\n",
    "                break\n",
    "        \n",
    "        period = len(ll) - 1 - i + 1\n",
    "\n",
    "        if n < i:\n",
    "            return toCell(ll[n])\n",
    "        else:\n",
    "            return toCell(ll[i + (n - i) % period])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        n = n % 14\n",
    "        if n == 0:\n",
    "            n = 14\n",
    "        for i in range(n):\n",
    "            if i == 1:\n",
    "                cells[0], cells[-1] = 0, 0\n",
    "            list_temp = [0]*8\n",
    "            for cell in range(1, len(cells) - 1):\n",
    "                if cells[cell - 1] == cells[cell + 1]:\n",
    "                    list_temp[cell] = 1\n",
    "                else:\n",
    "                    list_temp[cell] = 0\n",
    "            cells = list_temp\n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def prisonAfterNDays(self, cells, N):\n",
    "        def nextday(cells):\n",
    "            return [int(i > 0 and i < 7 and cells[i-1] == cells[i+1])\n",
    "                    for i in range(8)]\n",
    "\n",
    "        seen = {}\n",
    "        while N > 0:\n",
    "            c = tuple(cells)\n",
    "            if c in seen:\n",
    "                N %= seen[c] - N\n",
    "            seen[c] = N\n",
    "\n",
    "            if N >= 1:\n",
    "                N -= 1\n",
    "                cells = nextday(cells)\n",
    "\n",
    "        return cells"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells, N):\n",
    "        def nextday(cells):\n",
    "            return [int(i > 0 and i < 7 and cells[i-1] == cells[i+1])\n",
    "                    for i in range(8)]\n",
    "\n",
    "        seen = {}\n",
    "        while N > 0:\n",
    "            c = tuple(cells)\n",
    "            if c in seen:\n",
    "                N %= seen[c] - N\n",
    "            seen[c] = N\n",
    "\n",
    "            if N >= 1:\n",
    "                N -= 1\n",
    "                cells = nextday(cells)\n",
    "\n",
    "        return cells\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: list[int], n: int) -> list[int]:\n",
    "        new_status = [0] * len(cells)\n",
    "        n %= 14\n",
    "        if not n:\n",
    "            n = 14\n",
    "        for day in range(n):\n",
    "            for i in range(1, len(cells) - 1):\n",
    "                new_status[i] = cells[i - 1] ^ cells[i + 1] ^ 1\n",
    "            cells = copy.deepcopy(new_status)\n",
    "        return new_status\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    cells = [0, 1, 0, 1, 1, 0, 0, 1]\n",
    "    n = 7\n",
    "    print(obj.prisonAfterNDays(cells, n))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
